1. Field of the Invention
This invention relates to computational methods. More particularly this invention relates to the static analysis of the lifetimes of heap-allocated objects in functioning computer programs and the application of this analysis to generational garbage collection of heap memory.
2. Description of the Related Art
Current generational schemes of garbage collection allocate newly created objects on the heap to the youngest generation. If such an object survives a certain number of collections of that generation, it is promoted to an older generation. Older generations are collected less often. Promotion overhead continues to be paid until the object is either collected or it resides in the oldest generation. Generational garbage collection can be combined with various collection schemes, e.g., copying collection, mark-sweep collection, and the amount of overhead depends on the specific scheme.
For example, the primary overhead for a copying generational garbage collection, is the repeated copying of the object until it reaches the oldest generation.
In previous work, profiling of information has been proposed to estimate object lifetime. That estimation has then been used dynamically during the course of collection cycles to choose the proper generation in which to allocate the object. This scheme has been shown to indeed avoid the overhead associated with allocating a long-lived object in the youngest generation and then promoting it to an older generation. But this technique has significant drawbacks and incurs considerable runtime overhead. Profiling involves program instrumentation in order to train executions of a program, and further requires collecting and storing the results for later use. Such a process slows down the execution time, sometime by two order of magnitude, and is impractical for large programs. In addition, the results depends on the training input set.
The document Generational Stack Collection and Profile-Driven Pretenuring, P. Cheng, R. Harper, and P. Lee, PLDI ""98 pp. 162-173. proposes to use profiling to find object lifetimes and employ that information in order to improve a copying generational garbage collector. It discloses an average decrease of 30% in generational garbage collection time, through the avoidance of copying of data from generation to generation. It was noted that a few allocation sites consistently produce data that survive many allocations.
Recently the document A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks, S. Dieckmann, and Urs Holzle, Proceedings of the 13th European Conference on Object-Oriented Programming (ECOOP"" 99), Lisbon, June 1999, Springer Verlag, reports that 1%-40% of SPECjvm98 objects are still live after 100 Kbytes, with jess having the lower range and db on the upper end. Even after one megabyte of allocations, 21% of all allocated bytes are still live in javac, 12% in db and 8% in jack. These graphs show a flat age distribution after a drop at about 50 kbytes lasting until the end of the application. The possibility of eliminating expensive copying of large objects makes knowledge of object lifetime especially beneficial.
In other approaches attempts have been made to increase the efficiency of data flow analysis. Data flow analysis computes information about the potential behavior of a program in terms of the definitions and uses of data objects. Such data flow information is important for optimizing compilers, program environments, and understanding tools. It can also be used in a software-testing system or to provide compiler and runtime support for the parallel execution of programs originally written in sequential languages.
Numerous techniques have been successfully developed for data flow analysis of programs written in languages with only static data structures, such as Fortran. However, data flow analysis for programs written in languages with dynamically allocated data structures, such as C, C++, Fortran 90, Java (TM), and LISP, is more challenging because of pointer-induced aliasing, which occurs when two or more pointer expressions refer to the same storage location.
Aliasing occurs when there exists more than one access path to a storage location. An access path is constructed from variables, pointer dereference operators, and structure field selection operators. In C such an expression would include a variable with a possibly empty sequence of the following operators: xe2x80x9c*xe2x80x9d (dereference), xe2x80x9c.xe2x80x9d (field selection), and xe2x80x9cxe2x86x92xe2x80x9d (dereference and field selection). For purposes of pointer alias analysis, two access paths are xe2x80x9cmust-aliasesxe2x80x9d at a statement S if they refer to the same storage location in all execution instances of S. Two access paths are xe2x80x9cmay-aliasesxe2x80x9d at S if they refer to the same storage location in some execution instances of S.
A number of factors are known to influence the cost and precision of practical pointer alias analysis, including the use of flow sensitivity techniques, the use of context sensitivity, the manner in which aggregate data objects such as arrays and classes are modeled, the modeling of the heap, and the choice of alias representation. It is known that there is no general solution to the problem of pointer alias analysis, and the art has therefore attempted to improve the efficiency of the analysis using a variety of empirical and theoretical techniques and combinations. The document, Interprocedural Pointer Alias Analysis, Hind, Michael et al., ACM Transactions on Programming Languages, Vol. 21, No. 4, July 1999, proposes one combined approach to the analysis of pointer aliasing.
Pointer analysis has been found to be useful in understanding potential reachability connections between objects or references to objects. Recently, there has been a fair amount of work in developing algorithms for escape analysis of objects in Java (TM) programs to determine whether objects are local to the methods where they are created. Escape analysis is a static analysis that determines whether the object is still alive after the call to the method or procedure that created the object. The importance of escape analysis can be appreciated with reference to object oriented languages such as C++ and Java (TM), as their implementations often employ a garbage collector to assist in memory management. Java (TM) in particular relies on a garbage collector for heap-allocated objects. However garbage collectors are notoriously slow. Stack allocation of objects is one way to minimize garbage collection. It is an object of escape analysis to determine which objects can be stack allocated. A further use of escape analysis is to determine if an object is accessed only by a single thread during its lifetime in order to avoid unnecessary synchronization operations in a multithreaded or multiprocessor environment. A representative publication dealing with escape analysis is the document Escape Analysis for Object Oriented Languages. Application to Java (TM), Blanchet; B., OOPSLA 99.
The following two papers present various techniques that statically analyze objects in Java programs to determine whether they are local to the methods where they are created. These algorithms suggest various mapping techniques in applying escape analysis to reachability problems.
The document Escape Analysis for Java, J. D. Choi, M. Gupta, M. Serrano, V. O. Sreedhar, and S. Midkiff, OOPSLA ""99, pp. 1-19. reports that reachability and escape analysis specifies over 70% of all dynamically created objects as objects that may be allocated on the stack in three out of the ten benchmarks.
The document Removing Unnecessary Synchronization in Java, J. Bogda, and U. Holzle, OOPSLA ""99, pp. 20-34 discloses a static evaluation of escape analysis. The authors determined the percentage of candidate alias sets that were optimized. An ideal analysis, having no loss of precision, would reach 100% for a single threaded application. For the programs in their benchmark suite (compress, db, jack, javac, jess, mpegaudio, mtrt from SPECJvm98 in addition to sort and javaCup), the analysis was found to optimize between 91% and 96% of candidate alias sets.
Interprocedural data flow analyses make use of the program call graph (PCG), which is a flow multigraph in which each procedure is represented by a single node and in which an edge represents a potential call of a procedure from a call site of another procedure. In the presence of function pointers or virtual methods a call site may contribute multiple edges to different procedures.
There are many known methods for representing and computing interprocedural aliases for a program written in a language that includes pointers. Basically, during an interprocedural iteration, each procedure is visited, and intermediate intraprocedural information for the procedure is computed. This information is then used to update corresponding interprocedural information.
Preferred embodiments of the present invention teach an improved technique of data flow analysis using pointer analysis, which can be applied to improve the performance of generational garbage collection of heap memory.
The invention provides a computer implemented method of data flow analysis. An executing computer program employs pointers. Objects are allocated in memory by the program, and the objects are referenced by the pointers. Sizes of the objects are statically calculated at allocation sites in the program. A pointer alias analysis of the program is performed in order to estimate object lifetimes, wherein the estimated object lifetimes do not exceed actual lifetimes of the respective objects. Responsive to the pointer alias analysis and the static size calculation, the objects are assigned, or promoted, to an old generation or, in general, to any of an arbitrary number of generations which vary in age.
Pointer analysis has been the focus of many research works in the last couple of years, and there are many practical methods for representing and computing inter-procedural aliases for a program written in a language that includes pointers. Most implementations adopt an xe2x80x9cupper-boundxe2x80x9d approach for representing points-to information: They address all possible reachability connections that may happen in execution instances. This is done in order to ensure safety usage of the pointer analysis results.
In the context of this disclosure, there is no question of safety. There is only time-space tradeoff. At one extreme, in some embodiments the analysis is used very conservatively, in the sense that for every possible object that may be allocated during runtime, the statically estimated lifetime never exceeds the actual lifetime. In other words, a lower bound on the actual object lifetime is being sought. Such lower bound estimations might be too conservative and can result in insufficient reduction in the garbage collection overhead. At the other end, in other embodiments it may be chosen to promote an object to an older generation when the statically-estimated lifetime is computed as an upper bound, i.e. there is a computation path for which the estimated lifetime is correct.
Certain heuristics are adopted in order to control the various approaches. Lower bound, upper bound and xe2x80x9cmiddlexe2x80x9d estimations are handled by the heuristics. Using static branch predictor and the generation of xe2x80x9cmiddlexe2x80x9d estimations are suggested to give even better results.
An advantage of some aspects of the invention is the improved estimation of object lifetimes. It is known that the age distribution of objects exceeding about 50 kb is nearly flat. This, and the fact that more copying of such large objects takes place are further reasons to be aware of object lifetimes.
The application of some aspects of the invention result in a significant improvement in the static analysis of object lifetime to reduce garbage collection overhead.
These and other advantages of the present invention are attained by a technique for efficiently identifying objects that will persist for long periods of time. In an environment in which generational garbage collection is employed, exploitation of the knowledge of object lifetimes reduces the cost of repeatedly promoting the objects to older generations.
According to an aspect of the invention, the pointer alias analysis includes flow-sensitive analysis.
According to an additional aspect of the invention, an alias graph is iteratively constructed during the step of performing the pointer alias analysis until the alias graph is stable.
According to a further aspect of the invention, the alias graph is constructed by constructing a control flow graph for each analyzable element of the program. A hierarchy graph and a call graph are constructed for each analyzed code segment to determine the caller-callee relationships in the program. At each point in the code, a reachability graph is constructed for representing references to objects created at allocation sites.
According to yet another aspect of the invention, assignment is performed by locating possible garbage collection points in the code using the reachability graph. Paths are identified which extend from the allocation sites to the possible garbage collection points. The sizes of the objects are summed over the paths, and the objects are assigned to appropriate generations responsive to the summed sizes.
In another aspect of the invention, the step of assigning the objects to generations is performed by calculating a space that is allocated by each basic block of the program. The space for each block is accumulated and propagated, using in/out equations, and the objects are assigned responsive to the propagated accumulated space.
Preferably, the step of calculating sizes further includes the step of detecting dynamic loading of a class or, alternatively or additionally, detecting dynamic instantiation of an object, or detecting dynamic invocation of a method.
The pointer alias analysis may include either measuring a lower bound value of an object lifetime, measuring an upper bound value of an object lifetime, or measuring a value of an object lifetime that is intermediate an upper bound value thereof and a lower bound value thereof.
Although in preferred embodiments of the present invention, the methods of analysis described herein are used in promoting one or more of the objects to an older generation for purposes of garbage collection, the principles of the present invention may also be used to group the objects for other purposes.
The invention also provides a method of data flow analysis, including the steps of executing a program on a computer, determining a first point in the program that includes an allocation site of an object that is allocated on a heap memory, statically determining a second point in the program at which a given reachability criterion is satisfied with respect to the object, and statically computing the total amount of heap memory allocated on a path between the first point and the second point.
Preferably, the reachability criterion specifies that there is no reachable connection to the object at the second point. Alternatively, the reachability criterion specifies a heuristic likelihood of existence of a reachable connection to the object at the second point.
Responsive to the total amount of the heap memory, the object is assigned to one of a first group and a second group. In some embodiments there may be many groups to which the object can be assigned.
According to another aspect of the invention, the step of determining the second point is performed by pointer analysis. The pointer analysis includes the steps of constructing a control flow graph for an analyzable element of the program. constructing a hierarchy graph for each analyzable element, and constructing a call graph for the analyzable elements. Responsive to the control flow graph, the hierarchy graph and the call graph, a reachability graph is constructed for the analyzable elements.
According to a further aspect of the invention, static computation of object size is terminated when a computed lifetime exceeds a predetermined value.
According to an aspect of the invention, the step of statically determining a path to the second point is performed by identifying loops in the program that contain instructions for allocating the heap memory, and estimating a lower bound on a number of iterations traversed in the loops.
According to another aspect of the invention, the step of statically determining the second point is performed by predicting at least one frequently taken branch in the program, wherein the computation of the total amount of the heap memory is limited to the least frequently taken branch.
The methods according to the invention can be realized in a computer software product and executed on a general purpose computer with the computer software product resident therein.